package 双指针;

import java.util.Arrays;

public class 有效三角形个数5 {
    //https://leetcode.cn/problems/valid-triangle-number/
    public int triangleNumber(int[] nums) {
        int later = nums.length - 1;
        Arrays.sort(nums);
        int ret = 0;
        while(later >= 2) {
            int left = 0;
            int right = later - 1;
            while(left < right) {
                if (nums[left] + nums[right] > nums[later]) {
                    //nums[right]为数基 可直接排出结果
                    ret += right - left;
                    right--;
                }else {
                    //nums[left]为数基 直接排出必然非结果
                    left++;
                }
            }
            later--;
        }
        return ret;
    }
}
